'''
https://leetcode.cn/problems/largest-rectangle-in-histogram/description/
'''
from collections import deque
from typing import List


class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        ans = 0
        stack = deque()  # 栈中元素大压小 ,为了找左右比我小的位置
        for i, height in enumerate(heights):
            while stack and height <= heights[stack[-1]]:
                cur = stack.pop()
                # left + 1, ... right - 1， 这段区间内，nums[cur]最小值
                left = stack[-1] if stack else -1
                right = i
                ans = max(ans, heights[cur] * (right - left - 1))
            stack.append(i)
        while stack:
            cur = stack.pop()
            left = stack[-1] if stack else -1
            right = n
            ans = max(ans, heights[cur] * (right - left - 1))
        return ans
